home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / fw_squid.idb / usr / freeware / catman / p_man / cat3 / tree.Z / tree
Encoding:
Text File  |  1999-07-16  |  8.3 KB  |  199 lines
  1.  
  2.  
  3.  
  4.      TTTTRRRREEEEEEEE((((3333))))           UUUUNNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((5555    AAAApppprrrriiiillll 1111999999994444))))           TTTTRRRREEEEEEEE((((3333))))
  5.  
  6.  
  7.  
  8.      NNNNAAAAMMMMEEEE
  9.       tree_init, tree_mung,    tree_srch, tree_add, tree_delete,
  10.       tree_trav - balanced binary tree routines
  11.  
  12.      SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
  13.       vvvvooooiiiidddd
  14.       ttttrrrreeeeeeee____iiiinnnniiiitttt((((ttttrrrreeeeeeee))))
  15.       vvvvooooiiiidddd ********ttttrrrreeeeeeee;;;;
  16.  
  17.       vvvvooooiiiidddd ****
  18.       ttttrrrreeeeeeee____ssssrrrrcccchhhh((((ttttrrrreeeeeeee,,,, ccccoooommmmppppaaaarrrreeee,,,, ddddaaaattttaaaa))))
  19.       vvvvooooiiiidddd ********ttttrrrreeeeeeee;;;;
  20.       iiiinnnntttt ((((****ccccoooommmmppppaaaarrrreeee))))(((())));;;;
  21.       vvvvooooiiiidddd ****ddddaaaattttaaaa;;;;
  22.  
  23.       vvvvooooiiiidddd
  24.       ttttrrrreeeeeeee____aaaadddddddd((((ttttrrrreeeeeeee,,,, ccccoooommmmppppaaaarrrreeee,,,, ddddaaaattttaaaa,,,,    ddddeeeellll____uuuuaaaarrrr))))
  25.       vvvvooooiiiidddd ********ttttrrrreeeeeeee;;;;
  26.       iiiinnnntttt ((((****ccccoooommmmppppaaaarrrreeee))))(((())));;;;
  27.       vvvvooooiiiidddd ****ddddaaaattttaaaa;;;;
  28.       vvvvooooiiiidddd ((((****ddddeeeellll____uuuuaaaarrrr))))(((())));;;;
  29.  
  30.       iiiinnnntttt
  31.       ttttrrrreeeeeeee____ddddeeeelllleeeetttteeee((((ttttrrrreeeeeeee,,,, ccccoooommmmppppaaaarrrreeee,,,, ddddaaaattttaaaa,,,, ddddeeeellll____uuuuaaaarrrr))))
  32.       vvvvooooiiiidddd ********ttttrrrreeeeeeee;;;;
  33.       iiiinnnntttt ((((****ccccoooommmmppppaaaarrrreeee))))(((())));;;;
  34.       vvvvooooiiiidddd ****ddddaaaattttaaaa;;;;
  35.       vvvvooooiiiidddd ((((****ddddeeeellll____uuuuaaaarrrr))))(((())));;;;
  36.  
  37.       iiiinnnntttt
  38.       ttttrrrreeeeeeee____ttttrrrraaaavvvv((((ttttrrrreeeeeeee,,,, ttttrrrraaaavvvv____uuuuaaaarrrr))))
  39.       vvvvooooiiiidddd ********ttttrrrreeeeeeee;;;;
  40.       iiiinnnntttt ((((****ttttrrrraaaavvvv____uuuuaaaarrrr))))(((())));;;;
  41.  
  42.       vvvvooooiiiidddd
  43.       ttttrrrreeeeeeee____mmmmuuuunnnngggg((((ttttrrrreeeeeeee,,,, ddddeeeellll____uuuuaaaarrrr))))
  44.       vvvvooooiiiidddd ********ttttrrrreeeeeeee;;;;
  45.       vvvvooooiiiidddd ((((****ddddeeeellll____uuuuaaaarrrr))))(((())));;;;
  46.  
  47.      DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  48.       These    functions create and manipulate    a balanced binary
  49.       (AVL)    tree.  Each node of the    tree contains the expected
  50.       left & right subtree pointers, a short int balance
  51.       indicator, and a pointer to the user data.  On a 32 bit
  52.       system, this means an    overhead of 4+4+2+4 bytes per node
  53.       (or, on a RISC or otherwise alignment    constrained system
  54.       with implied padding,    4+4+4+4    bytes per node).  There    is no
  55.       key data type    enforced by this package; a caller supplied
  56.       compare routine is used to compare user data blocks.
  57.  
  58.       Balanced binary trees    are very fast on searches and
  59.       replacements,    but have a moderately high cost    for additions
  60.  
  61.  
  62.  
  63.      Page 1                         (printed 5/26/99)
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.      TTTTRRRREEEEEEEE((((3333))))           UUUUNNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((5555    AAAApppprrrriiiillll 1111999999994444))))           TTTTRRRREEEEEEEE((((3333))))
  71.  
  72.  
  73.  
  74.       and deletions.  If your application does a lot more searches
  75.       and replacements than    it does    additions and deletions, the
  76.       balanced (AVL) binary    tree is    a good choice for a data
  77.       structure.
  78.  
  79.       _T_r_e_e__i_n_i_t creates an empty tree and binds it to _t_r_e_e (which
  80.       for this and all other routines in this package should be
  81.       declared as a    pointer    to void    or int,    and passed by
  82.       reference), which can    then be    used by    other routines in this
  83.       package.  Note that more than    one _t_r_e_e variable can exist at
  84.       once;    thus multiple trees can    be manipulated simultaneously.
  85.  
  86.       _T_r_e_e__s_r_c_h searches a tree for    a specific node    and returns
  87.       either _N_U_L_L if no node was found, or the value of the    user
  88.       data pointer if the node was found.  _c_o_m_p_a_r_e is the address
  89.       of a function    to compare two user data blocks.  This routine
  90.       should work much the way _s_t_r_c_m_p(3) does; in fact, _s_t_r_c_m_p
  91.       could    be used    if the user data was a NUL terminated string.
  92.       _d_a_t_a is the address of a user    data block to be used by
  93.       _c_o_m_p_a_r_e as the search    criteria.  The tree is searched    for a
  94.       node where _c_o_m_p_a_r_e returns 0.
  95.  
  96.       _T_r_e_e__a_d_d inserts or replaces a node in the specified tree.
  97.       The tree specified by    _t_r_e_e is    searched as in _t_r_e_e__s_r_c_h, and
  98.       if a node is found to    match _d_a_t_a, then the _d_e_l__u_a_r function,
  99.       if non-NULL, is called with the address of the user data
  100.       block    for the    node (this routine should deallocate any
  101.       dynamic memory which is referenced exclusively by the    node);
  102.       the user data    pointer    for the    node is    then replaced by the
  103.       value    of _d_a_t_a. If no node is found to    match, a new node is
  104.       added    (which may or may not cause a transparent rebalance
  105.       operation), with a user data pointer equal to    _d_a_t_a. A
  106.       rebalance may    or may not occur, depending on where the node
  107.       is added and what the    rest of    the tree looks like.  _T_r_e_e__a_d_d
  108.       will return the _d_a_t_a pointer unless catastrophe occurs in
  109.       which    case it    will return NULL.
  110.  
  111.       _T_r_e_e__d_e_l_e_t_e deletes a    node from _t_r_e_e.    A rebalance may    or may
  112.       not occur, depending on where    the node is removed from and
  113.       what the rest    of the tree looks like.     _T_r_e_e__d_e_l_e_t_e returns
  114.       TRUE if a node was deleted, FALSE otherwise.
  115.  
  116.       _T_r_e_e__t_r_a_v traverses all of _t_r_e_e, calling _t_r_a_v__u_a_r with the
  117.       address of each user data block.  If _t_r_a_v__u_a_r    returns    FALSE
  118.       at any time, _t_r_e_e__t_r_a_v will immediately return FALSE to its
  119.       caller.  Otherwise all nodes will be reached and _t_r_e_e__t_r_a_v
  120.       will return TRUE.
  121.  
  122.       _T_r_e_e__m_u_n_g deletes every node in _t_r_e_e,    calling    _d_e_l__u_a_r    (if it
  123.       is not NULL) with the    user data address from each node (see
  124.       _t_r_e_e__a_d_d and _t_r_e_e__d_e_l_e_t_e above).  The    tree is    left in    the
  125.       same state that _t_r_e_e__i_n_i_t leaves it in - i.e., empty.
  126.  
  127.  
  128.  
  129.      Page 2                         (printed 5/26/99)
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.      TTTTRRRREEEEEEEE((((3333))))           UUUUNNNNIIIIXXXX SSSSyyyysssstttteeeemmmm VVVV ((((5555    AAAApppprrrriiiillll 1111999999994444))))           TTTTRRRREEEEEEEE((((3333))))
  137.  
  138.  
  139.  
  140.      BBBBUUUUGGGGSSSS
  141.       Should have a    way for    the caller to specify application
  142.       specific _m_a_l_l_o_c and _f_r_e_e functions to    be used    internally
  143.       when allocating meta data.
  144.  
  145.      AAAAUUUUTTTTHHHHOOOORRRR
  146.       Paul Vixie, converted    and augumented from Modula-2 examples
  147.       in _A_l_g_o_r_i_t_h_m_s    & _D_a_t_a _S_t_r_u_c_t_u_r_e_s, Niklaus Wirth,
  148.       Prentice-Hall, ISBN 0-13-022005-1.
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.      Page 3                         (printed 5/26/99)
  196.  
  197.  
  198.  
  199.